package com.linwen.excise.algorithm.贪心;

import java.util.Stack;

/**
 * leetcode 1221
 * <p>
 * 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
 * <p>
 * 给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
 * <p>
 * 每个子字符串都是平衡字符串。
 * 返回可以通过分割得到的平衡字符串的 最大数量 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "RLRRLLRLRL"
 * 输出：4
 * 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
 * 示例 2：
 * <p>
 * 输入：s = "RLRRRLLRLL"
 * 输出：2
 * 解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
 * 注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。
 * 示例 3：
 * <p>
 * 输入：s = "LLLLRRRR"
 * 输出：1
 * 解释：s 只能保持原样 "LLLLRRRR" 。
 */
public class _02 {
    public static void main(String[] args) {
        String s = "RLRRRLLRLL";
        System.out.println(balancedStringSplit2(s));
    }

    public static int balancedStringSplit(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        Stack<Character> stack = new Stack();
        for (int i = 0; i < chars.length; i++) {
            if (stack.isEmpty()) {
                stack.push(chars[i]);
            } else {
                if (stack.peek() == chars[i]) {
                    stack.push(chars[i]);
                } else {
                    stack.pop();
                }
            }
            if (stack.isEmpty()) {
                count++;
            }
        }
        return count;
    }

    public static int balancedStringSplit2(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        int balance = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'R') {
                balance++;
            }
            if (chars[i] == 'L') {
                balance--;
            }
            if (balance == 0) {
                count++;
            }
        }
        return count;
    }

}
